class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

import collections
class Solution(object):
    def deleteDuplicatesUnsorted(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        d = collections.defaultdict(int)
        node = head
        while node:
            d[node.val] += 1
            node = node.next
        pre_mut = ListNode(0, head)
        prev = pre_mut
        node = head
        while node:
            if d[node.val] > 1:
                prev.next = node.next
            else:
                prev = node
            node = node.next
        return pre_mut.next

